package com.learn.algorlthm;

/**
 * @classname:
 * @Description: 在O(1)时间内删除链表节点
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-07-24 09:55
 */
public class Learn18_1 {

    /**
     * 解题思路
     * <p>
     * 1.如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下个节点，再删除下一个节点，
     * 时间复杂度为O(1)
     * <p>
     * 2.否则就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向null，时间复杂度为O(N)。
     */

    public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
        if (head == null || head.next == null || tobeDelete == null)
            return null;
        if (tobeDelete.next != null) {
            //要删除的节点不是尾节点
            ListNode next = tobeDelete.next;
            tobeDelete.val = next.val;
            tobeDelete.next = next.next;
        } else {
            ListNode cur = head;
            while (cur.next != tobeDelete)
                cur = cur.next;
            cur.next = null;
        }

        return head;
    }

    class ListNode {
        public String val;
        public ListNode next;
    }

}
